package cn.com.forever.LinkedList;
/*
    给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替）
    例如：
    给定的二叉树是{1,2,3,#,#,4,5}
 */
import java.util.ArrayList;
import java.util.Stack;

public class BinaryTree_levelorder {
    public static void main(String[] args) {

    }

    public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot){
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        if(pRoot == null) return result;
        Stack<TreeNode> tmp = new Stack<>();
        Stack<TreeNode> tmp1 = new Stack<>();
        tmp.add(pRoot);
        while(tmp.size() >0 || tmp1.size() >0){
            ArrayList<Integer> flood = new ArrayList<>();
            if(tmp.size() > 0){
                int size = tmp.size();
                for (int i = 0; i < size; i++) {
                    TreeNode pop = tmp.pop();
                    flood.add(pop.val);
                    if(pop.left != null){
                        tmp1.push(pop.left);
                    }
                    if(pop.right != null){
                        tmp1.push(pop.right);
                    }
                }
                result.add(flood);
                continue;
            }
            if(tmp1.size() > 0){
                int size = tmp1.size();
                for (int i = 0; i < size; i++) {
                    TreeNode pop = tmp1.pop();
                    flood.add(pop.val);
                    if(pop.right != null){
                        tmp.push(pop.right);
                    }
                    if(pop.left != null){
                        tmp.push(pop.left);
                    }
                }
                result.add(flood);
                continue;
            }
        }
        return result;
    }
}
